package com.wenhao.leetcode.medium;


import java.util.*;

/**
 * 题目：课程表
 * https://leetcode-cn.com/problems/course-schedule/
 *
 * 拓扑排序
 *
 * @author Wenhao Tong
 * @create 2021-08-21 10:10
 */
public class LeetCode207 {
    List<List<Integer>> edges;
    int[] visited;
    boolean valid = true;
    /**
     * 记录入度
     */
    int[] indeg;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<>());
        }
        visited = new int[numCourses];
        // 如何建立一张图
        // 就是一个 List 每一个 index 的值表示当前节点指向的下一个节点
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return valid;
    }

    public boolean canFinish2(int numCourses, int[][] prerequisites) {
        indeg = new int[numCourses];
        edges = new ArrayList<>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<>());
        }
        // 如何建立一张图
        // 就是一个 List 每一个 index 的值表示当前节点指向的下一个节点
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
            indeg[info[0]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                queue.offer(i);
            }
        }

        int visited = 0;
        while (!queue.isEmpty()) {
            ++visited;
            int u = queue.poll();
            for (int v: edges.get(u)) {
                --indeg[v];
                // 删除queue里面的节点只需要修改queue连接的节点而不需要遍历整个数组
                if (indeg[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        return visited == numCourses;
    }

    public void dfs(int u) {
        visited[u] = 1;
        for (int v: edges.get(u)) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
                // 如果出现了正在访问中的节点，那么可以确定是有环的
            } else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }
}
